package org.codetranslators.common;

import java.util.Vector;

public abstract class DepthFirstSearch 
{
	protected DiGraph graph;
	protected Node startNode;
	
	private Object dfsResult;
	
	public abstract boolean isVisited(Edge edge);
	public abstract boolean isVisited(Node node);
	public abstract void visit(Edge edge);
	public abstract boolean isDone();
	public abstract void traverseDiscovery(Node nextNode, Node node);
	public abstract void traverseBack(Edge edge, Node node);
	
	public Object execute(DiGraph graph, Node startNode)
	{
		this.graph = graph;
		this.startNode = startNode;
		return null;
	}
	
	public Object traverse(Node node)
	{
		initResult();
		startVisit();
		visit(node);
		
		Vector outgoingEdges = graph.getOutgoingEdges(node);
		int numOutgoingEdges = 0;
		if(outgoingEdges != null) numOutgoingEdges = outgoingEdges.size();
		
		for(int i = 0; i < numOutgoingEdges; i++)
		{
			Edge nextEdge = (Edge) outgoingEdges.elementAt(i);
			if(!isVisited(nextEdge))
			{
				visit(nextEdge);
				Node nextNode = graph.getOppositeNode(node, nextEdge);
				if(!isVisited(nextNode))
				{
					traverseDiscovery(nextNode, node);
					if(!isDone())
						dfsResult = traverse(nextNode);
				}
				else
					traverseBack(nextEdge, node);
			}
		}
		finishVisit(node);
		return getResult();
	}
	
	public Object getResult() { return dfsResult;}
	
	public void initResult() {}
	public void startVisit() {}
	public void finishVisit(Node node) {}
	public void visit(Node node) {}

	
}
